package Method;

public class Main {

    public static void main(String []args){
        System.out.println("Hello World");
        int[] a = {12,20,5,16,15,1,30,45,23,9};
        int[] b = {2, 6, 9, 12, 13, 15, 17, 20, 32, 34, 35};
        int start = 0;
        int end = a.length-1;
    //    maopao(a,a.length);
        charu(a);
        for(int i = 0; i<a.length; i++){
            System.out.println(a[i]);
        }
        int res = erfen(b, 0, b.length-1, 33);
        System.out.println(res);

    }

    /**
     * 二分查找
     * @param group
     * @param left
     * @param right
     * @param target
     * @return
     */
    public static int erfen(int [] group, int left, int right, int target) {
        int mid = (left+right)/2;

        if(left <= right) {
            int midValue = group[mid];
            if(midValue < target) {
                return erfen(group, mid+1, right, target);
            } else if(midValue > target){
                return erfen(group, left, mid-1, target);
            } else {
                return mid;
            }
        } else {
            return -1;
        }
    }

    /**
     * 冒泡排序
     * @param group
     */
    public static void maopao(int [] group) {
        for(int i=0; i<group.length; ++i) {
            for(int j=0; j<group.length-i-1; ++j) {
                if(group[j] > group[j+1]) {
                    int temp = group[j];
                    group[j] = group[j+1];
                    group[j+1] = temp;
                }
            }
        }
    }

    /**
     * 插入排序
     * @param array
     */
    public static void charu(int[] array){
        for(int i =1;i<array.length;i++){
            int temp = array[i];
            int j = i-1;
            while(j>=0 && temp < array[j] ){
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = temp;
        }
    }

    /**
     * 选择排序
     * @param group
     */
    public static void xuanze(int [] group) {
        for(int i=0; i<group.length; ++i) {
            int min = 100000000;
            int minIndex = -1;
            for(int j=i; j<group.length; ++j) {
                if(group[j] < min) {
                    minIndex = j;
                    min = group[j];
                }
            }
            int temp = group[i];
            group[i] = group[minIndex];
            group[minIndex] = temp;
        }
    }

    /**
     * 快速排序
     * @param group
     * @param low
     * @param high
     */
    public static void quickSort(int [] group, int low, int high) {
        if(low < high) {
            int mid = slipGroup(group, low, high);
            quickSort(group, low, mid-1);
            quickSort(group, mid+1, high);
        }
    }

    public static int slipGroup(int [] group, int low, int high) {
        int i = low;
        int j = high+1;
        int patter = group[low];

        while (true) {
            while (group[++i] < patter) {
                if(i == high)
                    break;
            }
            while(group[--j] > patter) {
                if(j == low)
                    break;
            }

            if(i >= j)
                break;

            int temp = group[i];
            group[i] = group[j];
            group[j] = temp;

        }

        group[low] = group[j];
        group[j] = patter;

        return j;

    }

}
